package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class Code17_letterCombinations {
//    17. 电话号码的字母组合
//    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
//
//    给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
//    示例 1：
//
//    输入：digits = "23"
//    输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
//    示例 2：
//
//    输入：digits = ""
//    输出：[]
//    示例 3：
//
//    输入：digits = "2"
//    输出：["a","b","c"]

    // 存储输入的数字字符串
    private String digits;
    // 存储最终的结果集
    private List<String> res;
    // 数字到字母的映射数组
    private String[] numbers;
    // 用于构建当前组合的字符串
    private StringBuilder str;

    /**
     * 主函数，用于生成数字字符串对应的字母组合
     * @param digits 输入的数字字符串
     * @return 所有可能的字母组合
     */
    public List<String> letterCombinations(String digits) {
        this.digits = digits;
        this.res = new ArrayList<>();
        // 如果输入为空，则直接返回空的结果集
        if (digits == null || digits.length() == 0){
            return res;
        }
        // 初始化数字到字母的映射
        numbers = new String[] {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        str = new StringBuilder();
        // 从第一个数字开始深度优先搜索
        dfs(0);
        return res;
    }

    /**
     * 深度优先搜索函数，用于生成字母组合
     * @param currIndex 当前处理的数字字符在digits中的索引
     */
    private void dfs(int currIndex) {
        // 如果当前索引等于输入字符串长度，说明已经构建了一个完整的组合
        if (currIndex == digits.length()){
            res.add(str.toString());
            return;
        }
        // 获取当前数字对应的所有可能的字母
        for (char c : numbers[digits.charAt(currIndex) - '2'].toCharArray()){
            // 将当前字母添加到组合中
            str.append(c);
            // 继续处理下一个数字字符
            dfs(currIndex + 1);
            // 回溯，移除最后一个字母，尝试下一个可能的字母
            str.deleteCharAt(str.length() - 1);
        }
    }


    public static void main(String[] args) {
        Code17_letterCombinations letterCombinations = new Code17_letterCombinations();
        System.out.println(letterCombinations.letterCombinations("23"));
    }

}
